﻿using ListNode;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace IsValidBST
{
    //    给定一个二叉树，判断其是否是一个有效的二叉搜索树。

    //假设一个二叉搜索树具有如下特征：

    //节点的左子树只包含小于当前节点的数。
    //节点的右子树只包含大于当前节点的数。
    //所有左子树和右子树自身必须也是二叉搜索树。
    class Program
    {
        static void Main(string[] args)
        {
            TreeNode t1 = new TreeNode(10);
            t1.left = new TreeNode(5);
            t1.right = new TreeNode(15);
            t1.right.left = new TreeNode(6);
            t1.right.right = new TreeNode(20);
            Console.WriteLine(IsValidBST(t1));
            Console.ReadKey();
        }
        public static bool IsValidBST(TreeNode root)
        {
            if (root == null) return true;
            if (root.left == null)
            {
                if (root.right == null)
                {
                    return true;
                }
                else
                {
                    if (root.right.val > root.val)
                    {
                        return true && IsValidBST(root.left) && IsValidBST(root.right);
                    }
                    else
                    {
                        return false;
                    }
                }

            }
            else
            {
                if (root.right == null)
                {
                    if (root.left.val < root.val)
                    {
                        return true && IsValidBST(root.left) && IsValidBST(root.right);
                    }
                    else
                    {
                        return false;
                    }
                }
                else
                {
                    if (root.left.val < root.val && root.right.val > root.val)
                    {
                        return true && IsValidBST(root.left) && IsValidBST(root.right);
                    }
                    else
                    {
                        return false;
                    }
                }
            }

        }
        public static bool Valid(TreeNode node)
        {
            if (node.left.val < node.val && node.right.val > node.val)
            {
                return true && Valid(node.left) && Valid(node.right);
            }
            else
            {
                return false;
            }
        }
    }
}
